package _021_10_6

import "sort"

type pair2 struct {
	val  int
	node *ListNode
}
type pairSlice []pair2

func (p pairSlice) Len() int {
	return len(p)
}

func (p pairSlice) Less(i, j int) bool {
	if p[i].val < p[j].val {
		return true
	}
	return false
}

func (p pairSlice) Swap(i, j int) {
	temp := p[i]
	p[i] = p[j]
	p[j] = temp
}

type ListNode struct {
	Val  int
	Next *ListNode
}

func sortInList(head *ListNode) *ListNode {
	// write code here
	var data pairSlice
	node := head
	for node != nil {
		data = append(data, pair2{node.Val, node})
		node = node.Next
	}
	sort.Sort(data)
	newH := new(ListNode)
	t := newH
	for i := 0; i < len(data); i++ {
		newH.Next = data[i].node
		newH = newH.Next
	}
	newH.Next = nil
	return t.Next
}
